/***
 * 自定义数组
 */
public class Array<T> {
    private T[] data;
    private int size;

    public Array(int capacity){
        data = (T[])new Object[capacity];
        size = 0;
    }

    public Array(){
        this(10);
    }

    public int getSize(){
        return this.size;
    }
    public int getCapacity(){
        return this.data.length;
    }
    public boolean isEmpty(){
        return size == 0;
    }

    //向数组的末尾添加元素
    public void addLast(T e){
        add(size,e);
    }
    //向数组的开头添加元素
    public void addFirst(T e){
        add(0,e);
    }
    //在第index位置插入元素
    public void add(int index,T e){
        //判断参数是否合法
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Array addLast error,Required index >= 0 and index < size");
        }
        //判断数组是否还有剩余空间
        if(size == data.length){
//            throw new IllegalArgumentException("Array addLast error,Array is full");
            //给Array2倍扩容
            resize(2*data.length);
        }
        //将index往后的元素都后移一位
        for(int i=size-1;i>=index;i--){
            data[i+1] = data[i];
        }
        data[index] = e;
        size++;
    }

    private void resize(int newCapacity) {
        T[] newdata = (T[]) new Object[newCapacity];
        for(int i = 0;i<size;i++){
            newdata[i] = data[i];
        }
        data = newdata;
    }

    @Override
    public String toString() {
        StringBuffer sb =new StringBuffer();
        sb.append(String.format("Array: size = %d,capacity = %d\n",size,data.length));
        sb.append("[");
        for(int i=0;i<size;i++){
            sb.append(data[i]);
            if(i != size - 1){
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    //获取index索引位置的元素
    public T get(int index){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Get Error,index is Illiegal");
        }
        return data[index];
    }

    public T getLast(){
        return get(size - 1);
    }

    public T getFirst(){
        return get(0);
    }
    //设置元素值
    public void set(int index,T e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Get Error,index is Illiegal");
        }
        data[index] = e;
    }

    //数组中是否包含某元素
    public boolean contains(T e){
        for(int i=0;i<size;i++){
            if(data[i].equals(e)){
                return true;
            }
        }
        return false;
    }

    //查找数组中某元素的位置
    public int find(T e){
        for(int i=0;i<size;i++){
            if(data[i].equals(e)){
                return i;
            }
        }
        return -1;
    }

    //从数组中删除index位置的元素,并将该元素返回
    public T remove(int index){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Remove Error,index is Illiegal");
        }
        T rm = data[index];
        //将index后面的元素前移
        for (int i=index+1;i<size;i++){
            data[i - 1] = data[i];
        }
        size --;
        data[size] = null;
        //若data.length/2 == size,1/2缩容
        if(size == data.length / 4 && data.length /2 != 0){
            resize(data.length / 2);
        }
        return rm;
    }
    public T removeFirst(){
        return remove(0);
    }
    public T removeLast(){
        return remove(size - 1);
    }
    //从数组中删除元素e
    public void removeElement(T e){
        int index = find(e);
        if(index != -1){
            remove(index);
        }
    }

}
